class Solution {
    public int fib(int n) {
        final int MOD = 1000000007;
        if(n == 0 || n == 1) {
            return n;
        }
        int[] a = new int[n+1];
        a[0] = 0;
        a[1] = 1;
        for(int i = 2;i <= n;i++) {
            a[i] = (a[i-1] + a[i-2]) % MOD;
        }
        return a[n];
    }
}